package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class S7 {
    //大顶堆
    //维护堆的性质
    //传入值 iNt[] arr  数组长度n 下标i
    public void heapify(int[]arr,int n ,int i) {
        int largest = i;
        int lson = i*2+1;
        int rson = i*2+2;
        if(lson<n && arr[largest]<arr[lson]) {
            largest = lson;
        }else if(rson<n && arr[largest]<arr[rson]) {
            largest = rson;

        }
        if(largest != i){
//            swap(arr,arr[i],arr[largest]);
            heapify(arr,n,largest);
        }
    }
    public void  heap_sort(int[] arr,int n) {
        //1.建堆
        //遍历元素使用每个元素都维护大顶堆
        // (n-1-1)/2
        for (int i = n/2 -1; i >0 ; i--) {
            heapify(arr,n,i);
        }
        //2.排序
        //每次交换最后元素与首元素(大顶堆根节点)--->交换后最大值的节点拿出来弹出
        for (int i = n-1; i >0 ; i--) {
//            swap(arr,arr[i],arr[0]);
            heapify(arr,i,i);
        }
    }

    public static void main(String[] args) {
        int[] arr  = {1,2,3,4};
        ArrayList list = new ArrayList(Arrays.asList(arr));

        ArrayList arrList =  new ArrayList(Arrays.asList(arr));

    }
}

